package leetcode.code1552;

import java.util.Arrays;

public class Solution {
	public int maxDistance(int[] position, int m) {
		Arrays.sort(position);
		int ans = 0, l = 0, r = position[position.length - 1] - 1;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			int cnt = 1, last = position[0];
			for (int i = 1; i < position.length; i++) {
				if (position[i] >= last + mid) {
					cnt++;
					last = position[i];
				}
			}
			if (cnt >= m) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return ans;
	}
}
